package cn.xdf.learn.leetcode.两数相加;

import java.util.ArrayList;
import java.util.List;

public class Solution {


    /**
     * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
     * <p>
     * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
     * <p>
     * 你可以按任意顺序返回答案。
     * <p>
     * 示例 1：
     * <p>
     * 输入：nums = [2,7,11,15], target = 9
     * 输出：[0,1]
     * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
     * 示例 2：
     * <p>
     * 输入：nums = [3,2,4], target = 6
     * 输出：[1,2]
     * 示例 3：
     * <p>
     * 输入：nums = [3,3], target = 6
     * 输出：[0,1]
     * 提示：
     * <p>
     * 2 <= nums.length <= 104
     * -109 <= nums[i] <= 109
     * -109 <= target <= 109
     * 只会存在一个有效答案
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        List<ListNode> list1 = new ArrayList<>();
        List<ListNode> list2 = new ArrayList<>();
        setList(list1, l1);
        setList(list2, l2);

        List<Integer> dataList = new ArrayList<>();
        int size = list1.size() > list2.size() ? list1.size() : list2.size();

        //进一位
        int carry = 0;
        for (int i = 0; i < size; i++) {

            int a = 0;
            int b = 0;
            if (i < list1.size()) {
                a = list1.get(i).val;
            }
            if (i < list2.size()) {
                b = list2.get(i).val;
            }
            int d = a + b;
            d = d + carry;
            if (d > 9) {
                d = d - 10;
                dataList.add(d);
                carry = 1;
            } else {
                dataList.add(d);
                carry = 0;
            }

        }

        //最后一位进一位
        if (carry == 1) {
            dataList.add(Integer.valueOf(1));
        }

        //将list转换成链表
        ListNode result = new ListNode();
        ListNode tmp = result;
        for (int i = 0; i < dataList.size(); i++) {
            tmp.val = dataList.get(i);
            if (i != dataList.size() - 1) {
                tmp.next = new ListNode();
                tmp = tmp.next;
            }
        }
        return result;


    }

    private void setList(List<ListNode> list, ListNode node) {
        if (node.next != null) {
            list.add(node);
            setList(list, node.next);
        } else {
            list.add(node);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.addTwoNumbers(new ListNode(2, new ListNode(4, new ListNode(9))),
                new ListNode(5, new ListNode(6, new ListNode(4, new ListNode(9)))));
    }

}
